8.9 KB · ⇊ 4 parts · ⤓ Micron 8.9 KB · ⤓ HTML 73.9 KB

top

Die fast konvexen Funktionen (englisch convex-like functions) bilden eine Verallgemeinerung der konvexen Funktionen und werden in der mathematischen Optimierung verwendet, da für sie einfache Regularitätsvoraussetzungen wie die Slater-Bedingung gelten, unter denen starke Dualität gilt und damit auch die Karush-Kuhn-Tucker-Bedingungen gelten.

• Definition

• Beispiele

• Eigenschaften

• Verwendung

• Literatur

Seien V 1 , V 2 {\displaystyle V_{1},V_{2}} reelle Vektorräume und K {\displaystyle K\,} ein Ordnungskegel auf V 2 {\displaystyle V_{2}} sowie D 1 {\displaystyle D_{1}} eine nichtleere Teilmenge von V 1 {\displaystyle V_{1}} . Dann heißt eine Abbildung f : : D 1 ↦ ↦ V 2 {\displaystyle f\colon D_{1}\mapsto V_{2}} fast konvex, wenn die Menge

M := f ( D 1 ) + K {\displaystyle M:=f(D_{1})+K}

konvex ist. Die Menge M {\displaystyle M} lässt sich äquivalent beschreiben als

M = { y ∈ ∈ V 2 | ∃ ∃ x ∈ ∈ D 1 so dass f ( x ) − − y ∈ ∈ − − K } {\displaystyle M=\{y\in V_{2}\,|\,\exists x\in D_{1}{\text{ so dass }}f(x)-y\in -K\}}

Ist der Kegel ein echter Kegel und definiert damit eine verallgemeinerte Ungleichung ≼ ≼ K {\displaystyle \preccurlyeq _{K}} , so lautet diese Menge

M = { y ∈ ∈ V 2 | ∃ ∃ x ∈ ∈ D 1 so dass f ( x ) ≼ ≼ K y } {\displaystyle M=\{y\in V_{2}\,|\,\exists x\in D_{1}{\text{ so dass }}f(x)\preccurlyeq _{K}y\}}

Betrachtet man die Funktion f : : R ↦ ↦ R {\displaystyle f\colon \mathbb {R} \mapsto \mathbb {R} } mit f ( x ) = sin ⁡ ⁡ ( x ) {\displaystyle f(x)=\sin(x)} und den echten Kegel K = R + = { x ∈ ∈ R | x ≥ ≥ 0 } {\displaystyle K=\mathbb {R} _{+}=\{x\in \mathbb {R} \,|\,x\geq 0\}} sowie D 1 = [ 0 , 2 π π ] {\displaystyle D_{1}=[0,2\pi ]} , so ist sin ⁡ ⁡ ( D 1 ) = [ − − 1 , 1 ] {\displaystyle \sin(D_{1})=[-1,1]} . Damit ist M = [ − − 1 ; 1 ] + R + = { x ∈ ∈ R | x ≥ ≥ − − 1 } {\displaystyle M=[-1;1]+\mathbb {R} _{+}=\{x\in \mathbb {R} \,|\,x\geq -1\}} . Diese Menge ist konvex und damit ist die Sinusfunktion fast konvex.

Betrachtet man die Funktion f ( x ) = { − − 1 falls x ≤ ≤ 0 1 falls x > 0 {\displaystyle f(x)={\begin{cases}-1&{\text{ falls }}x\leq 0\\1&{\text{ falls }}x>0\end{cases}}}

und definiert g : : R ↦ ↦ R 2 {\displaystyle g\colon \mathbb {R} \mapsto \mathbb {R} ^{2}} durch

g ( x ) = ( f ( x ) 5 x ) {\displaystyle g(x)={\begin{pmatrix}f(x)\\5x\end{pmatrix}}}

auf D 0 = R {\displaystyle D_{0}=\mathbb {R} } mit dem Ordnungskegel K = R + × × { 0 } {\displaystyle K=\mathbb {R} _{+}\times \{0\}} . Für x ∈ ∈ D 1 = { x ∈ ∈ R | x ≤ ≤ 0 } {\displaystyle x\in D_{1}=\{x\in \mathbb {R} \,|\,x\leq 0\}} ist jeder Punkt der Bildmenge von der Form ( − − 1 , 5 x ) {\displaystyle (-1,5x)} und damit ist g ( D 1 ) = { y ∈ ∈ R 2 | y 1 = − − 1 , y 2 ≤ ≤ 0 } {\displaystyle g(D_{1})=\{y\in \mathbb {R} ^{2}\,|\,y_{1}=-1,y_{2}\leq 0\}} . Analog folgt mit D 2 = { x ∈ ∈ R | x > 0 } {\displaystyle D_{2}=\{x\in \mathbb {R} \,|\,x>0\}} , dass g ( D 2 ) = { y ∈ ∈ R 2 | y 1 = 1 , y 2 > 0 } {\displaystyle g(D_{2})=\{y\in \mathbb {R} ^{2}\,|\,y_{1}=1,y_{2}>0\}} . Somit ist

g ( D 1 ) + K = { y ∈ ∈ R 2 | y 1 ≥ ≥ − − 1 , y 2 ≤ ≤ 0 } g ( D 2 ) + K = { y ∈ ∈ R 2 | y 1 ≥ ≥ 1 , y 2 > 0 } {\displaystyle {\begin{aligned}g(D_{1})+K=\{y\in \mathbb {R} ^{2}\,|\,y_{1}\geq -1,y_{2}\leq 0\}\\g(D_{2})+K=\{y\in \mathbb {R} ^{2}\,|\,y_{1}\geq 1,y_{2}>0\}\end{aligned}}}

Da aber D 0 = D 1 ∪ ∪ D 2 {\displaystyle D_{0}=D_{1}\cup D_{2}} ist, kann die Menge g ( D 0 ) + K = g ( D 1 ∪ ∪ D 2 ) + K = ( g ( D 1 ) + K ) ∪ ∪ ( g ( D 2 ) + K ) {\displaystyle g(D_{0})+K=g(D_{1}\cup D_{2})+K=\left(g(D_{1})+K\right)\cup \left(g(D_{2})+K\right)} nicht konvex sein, da zum Beispiel die Punkte ( − − 1 , 0 ) T {\displaystyle (-1,0)^{T}} und ( 1 , 1 ) T {\displaystyle (1,1)^{T}} in g ( D 0 ) + K {\displaystyle g(D_{0})+K} enthalten sind, aber keiner der Punkte auf der Strecke zwischen ihnen. Zum Beispiel ist ( 0 , 0 , 5 ) {\displaystyle (0,0{,}5)} der Mittelpunkt dieser Strecke, aber nicht in g ( D 0 ) + K {\displaystyle g(D_{0})+K} enthalten.

Jede konvexe Funktion ist fast konvex bezüglich des natürlichen Kegels K = R + {\displaystyle K=\mathbb {R} _{+}} . Dies folgt direkt aus der Konvexität des Epigraphs. Genauso ist auch jede K-konvexe Funktion fast konvex bezüglich ihres Kegels.

Die fast konvexen Funktionen sind eine Funktionenklasse, die so definiert ist, dass wenn sie die Slater-Bedingung erfüllt, die starke Dualität gilt. Sei also ein Optimierungsproblem der Form

Minimiere f ( x ) unter den Nebenbedingungen g ( x ) ∈ ∈ − − K x ∈ ∈ R {\displaystyle {\begin{aligned}{\text{Minimiere }}&f(x)\\{\text{unter den Nebenbedingungen }}&g(x)\in -K\\&x\in R\end{aligned}}}

gegeben für einen Ordnungskegel K {\displaystyle K\,} mit nichtleerem Inneren und Abbildungen f : : V ↦ ↦ R {\displaystyle f\colon V\mapsto \mathbb {R} } und g : : V ↦ ↦ Y {\displaystyle g\colon V\mapsto Y} . Dabei sind V , Y {\displaystyle V,Y} normierte reelle Vektorräume und die Funktion K : : V ↦ ↦ R × × Y {\displaystyle K\colon V\mapsto \mathbb {R} \times Y} definiert durch K ( x ) = ( f ( x ) , g ( x ) ) {\displaystyle K(x)=(f(x),g(x))} ist fast konvex bezüglich des Kegels R + × × K {\displaystyle \mathbb {R} _{+}\times K} . Weiter sei R {\displaystyle R} eine beliebige nichtleere Teilmenge von V {\displaystyle V} .

Das Problem erfüllt nun die Slater-Bedingung, wenn es einen zulässigen Punkt x ~ ~ {\displaystyle {\tilde {x}}} gibt. Das heißt x ~ ~ ∈ ∈ R , g ( x ~ ~ ) ∈ ∈ − − K {\displaystyle {\tilde {x}}\in R,\,g({\tilde {x}})\in -K} , so dass g ( x ~ ~ ) ∈ ∈ int ⁡ ⁡ ( − − K ) {\displaystyle g({\tilde {x}})\in \operatorname {int} (-K)} ist. Dabei bezeichnet int ⁡ ⁡ ( M ) {\displaystyle \operatorname {int} (M)} das Innere einer Menge.

Erfüllt solch ein Problem mit fast konvexen Funktionen nun die Slater-Bedingung, so gilt starke Dualität und damit zum Beispiel auch die Karush-Kuhn-Tucker-Bedingungen. Der Begriff der fast konvexen Funktion erweitert also die Dualitätstheorie der konvexen Funktionen auf Probleme, die nicht notwendigerweise konvex sein müssen. Dies hat den Vorteil, dass die Slater-Bedingung im Gegensatz zu vielen anderen Regularitätsbedingungen oder „constraint qualifications“ die Regularität des gesamten Problemes liefert, und nicht nur die Regularität in einem Punkt.

• Johannes Jahn: Introduction to the Theory of Nonlinear Optimization. 3. Auflage. Springer, Berlin 2007, ISBN 978-3-540-49378-5.